#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> arr;
void show(vector<int> &arr)
{
    for (auto &it : arr)
        printf(" %d", it);
    printf("\n");
};
void qSort(vector<int> &arr, int l, int r)
{
    if (l >= r)
        return;
    swap(arr[r], arr[(l + r) / 2]);
    int i = l - 1, pivot = arr[r];
    for (int j = l; j < r; ++j)
        if (pivot > arr[j])
            swap(arr[++i], arr[j]);
    swap(arr[i + 1], arr[r]);
    qSort(arr, l, i);
    qSort(arr, i + 2, r);
}
int main()
{
    arr = {9, 3, 2, 4, 5, 6, 3, 1};
    show(arr);
    qSort(arr, 0, arr.size() - 1);
    show(arr);
    return 0;
}